module MergeSort;

import tango.io.Stdout;
//import tango.io.Console;
import tango.util.Convert;
import tango.math.Math;
// uwaga to jest werja dla Tango 99.6 bo w 99.7 
// jest juz zmiana w random i powinno sie korzystac 
// z tango.math.random.Kiss;
import tango.math.Random;  
import tango.core.Thread;
import tango.core.sync.Barrier;

import tango.util.log.Trace;


/**
 * start pierwszy indeks
 * koniec - ostatni indeks
 * tylko elementy pomiedzy start i koniec (wlacznie) beda posortowane
 */
void mergeSort(inout int[] tab, int start, int koniec){
	if (tab.length == 0) return tab;
	if (start == koniec) return tab;
	int srodek = (koniec + start) / 2; //(podloga)
	mergeSort(tab, start, srodek);
	mergeSort(tab, srodek + 1, koniec);
	merge(tab, start, srodek, srodek + 1, koniec);
}

void merge(inout int[] tab, int aStart, int aKoniec, int bStart, int bKoniec) {
	int[] toReturn;
	int i = aStart;
	int j = bStart;
	
	while ((i <= aKoniec) && (j <= bKoniec)) {
		if (tab[i] < tab[j]) {
			toReturn ~= tab[i];
			i++;
		} else {
			toReturn ~= tab[j];
			j++;
		}
	}
	
	while (i <= aKoniec) {
		toReturn ~= tab[i++];
	}
	while (j <= bKoniec) {
		toReturn ~= tab[j++];
	}
	int k = 0;
	while (k < toReturn.length){
		tab[aStart + k] = toReturn[k];
		k++;
	}
	
	return toReturn;
}

class MergeThread : Thread{
	int id;
	int runda;
	int[] tab;
	int[] tabWymiana;
	
	this(int id, int[] tab, int runda = 0){
		super( &run );
		this.id = id;
		this.tab = tab;
		this.runda = runda;
	}

private:
	void run(){
		if (runda == 0) mergeSort(tab, 0, tab.length - 1);
		//parallelMergeSort();
		parallelMerge(runda);
	}
	
	void parallelMerge(int nrRundy){
		int dwaDoItej = to!(int)(pow(to!(real)(2), nrRundy));
		
		if ((this.id & dwaDoItej) > 0) {
			debug Trace.formatln("HIGH: id: {} (id & dwaDoItej) = {}", id, (id & dwaDoItej));
			compereExchange(0, nrRundy);
		} else {
			debug Trace.formatln("LOW id: {} (id & dwaDoItej) = {}", id, id & dwaDoItej);
			compereExchange(1, nrRundy);
		}
	}
	
	void compereExchange(int lowOrHigh, int nrRundy) {
		int zKimWymienic = id ^ to!(int)(pow(to!(real)(2), nrRundy)); // ^ == XOR
		debug Trace.formatln("{}: wymieniam z {}", id, zKimWymienic);
		auto tabSasiada = threadTable[zKimWymienic].tab;
		
		int dl = tab.length;
		int[] tabSort;
		tabSort ~= tab;
		tabSort ~= tabSasiada;
		mergeSort(tabSort, 0, tabSort.length - 1);
		//Trace.formatln("{}: tabSort: {}	", id, tabSort);
		//Trace.formatln("{}: lowOrHigh: {}	", id, lowOrHigh);
		tabWymiana = tabSort;
		//Trace.formatln("{}: tabWymiana ----- to check: {}	", id, tabWymiana);
	}
}


/*********************
 *       MAIN        *
 *********************/

MergeThread[] threadTable;
int nrRundy;

int main(char[][] args){
	if (3 != args.length) {
		Stdout ("Usage: ")/*(args[0])*/("MergeSort.exe")(" <ilosc_elementow_w_tablicy_kazdego_watku> <potega>").newline;
		return 1;
	}
	
	int dlTabWatku = to!(int)(args[1]);
	int potega = to!(int)(args[2]);
	
	if (dlTabWatku <= 0) {
		Stdout.formatln("ilosc_elementow_w_tablicy_kazdego_watku (dlTabWatku = {})", dlTabWatku);
		return 1;
	}
	if (potega < 0) {
		Stdout.formatln("zla potega (potega = {})", potega);
		return 1;
	}
	int iloscWatkow = to!(int)(pow(to!(real)(2), potega));
	
	int[] tablica;
	tablica.length = dlTabWatku * iloscWatkow;
	
	// Generowanie losowej zawartosci tablicy
	auto rand = new Random();
	for(int i = 0; i < tablica.length; i++){
		tablica[i] = rand.next(100);
	}
	
	// sortowanie jednowatkowe (2 do potegi 0 == 1)
	if (potega == 0) {
		Stdout (tablica).newline;
		mergeSort(tablica, 0, tablica.length -1);
		Stdout ("posortowana:")(tablica).newline;
		return 0;
	}
	
	// sortowanie wielowatkowe
	auto tg = new ThreadGroup();
	
	threadTable.length = iloscWatkow;
	// tworzymy odpowiednia ilosc watkow
	for (int i = 0; i < iloscWatkow; i++) {
		threadTable[i] = new MergeThread(i, tablica[i*dlTabWatku .. i * dlTabWatku + dlTabWatku]);
		debug Trace.formatln("i: {} tablica: {}", i, tablica[i*dlTabWatku .. i * dlTabWatku + dlTabWatku]);
	}
	
	// zapisujemy je do grupy wa
	foreach(thread; threadTable){
		tg.add(thread);
	}
	for(int i = 0; i < potega; i++) {
		foreach(thread; threadTable){
			thread.start();
		}
		tg.joinAll();
		foreach(thread; threadTable){
			thread.tab = thread.tabWymiana;
			thread.runda++;
		}
	}
	
	Trace.formatln("do posortowania:\n{}", tablica);
	for (int i = 0; i < iloscWatkow; i++) {
		Trace.formatln("{}:\n{}", i, threadTable[i].tab);
	}
	
	mergeSort(tablica, 0, tablica.length -1);
	Trace.formatln("postortowana:\n{}", tablica);
	
	return 0;
}